package com.gaogzhen.algorithms4.sort;

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;


/**
 * 插入排序
 * 思想：希尔排序的思想是使任意间隔h的元素都是有序的。这样的数组被称为h有序数组。
 * 算法：
 * 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
 * 按增量序列个数k，对序列进行k 趟排序；
 * 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
 */
public class MergeImprovement {

    // 阈值15，数组小于15使用插入排序
    private static final int THRESHOLD = 15;

    /**
     * 排序方法
     * @param a     实现了Comparable接口的待排序数组
     */
    public static void sort(Comparable[] a) {
        Comparable[] aux = a.clone();
        sort(aux, a, 0, a.length - 1);

    }

    /**
     * 对子数组排序
     * @param src     辅助数组
     * @param dest    结果数组
     * @param lo    子数组索引起始
     * @param hi    子数组索引终止
     */
    private static void sort(Comparable[] src, Comparable[] dest, int lo, int hi) {
        // 把数组a[lo...hi]排序
        if ((hi - lo) < THRESHOLD) {
            // 数组长度小于阈值，使用插入排序
            insertion(dest, lo, hi);
            return;
        }
        int mid = lo + (hi - lo) / 2;
        // 左半边数组排序
        sort(dest, src, lo, mid);
        // 右半边数组排序
        sort(dest, src, mid + 1, hi);
        // 归本结果
        if (less(src[mid], src[mid+1])) return;
        merge(src, dest, lo, mid, hi);
    }

    private static void insertion(Comparable[] a, int lo, int hi) {
        int N = a.length;
        for (int i = lo; i <= hi; i++) {
            for (int j = i ; j > lo && less(a[j], a[j - 1]);  j--) {
                exch(a, j, j - 1);
            }

        }
    }

    /**
     * 归并以排序的两个子数组
     * @param src         辅助数组
     * @param src         结果数组
     * @param lo        子数组1起始索引
     * @param mid       子数组1终止索引，mid+1子数组2起始索引
     * @param hi        子数组2终止索引
     */
    private static void merge(Comparable[] src, Comparable[] dest, int lo, int mid, int hi) {
        // 将a[lo...mid]和a[mid+1...hi]归并
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (i > mid) dest[k] = src[j++];
            else if (j > hi) dest[k] = src[i++];
            else if (less(src[j], src[i])) dest[k] = src[j++];
            else dest[k] = src[i++];
        }
    }

    /**
     * 比较大小
     * @param a     目标a
     * @param b     目标b
     * @return      返回布尔值
     */
    private static  boolean less(Comparable a, Comparable b) {
        return a.compareTo(b) < 0;
    }

    /**
     * 交换数组元素
     * @param a     数组
     * @param i     索引
     * @param j     索引
     */
    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    /**
     * 打印数组
     * @param a     数组
     */
    private static void show(Comparable[] a) {
        // 单行打印数组
        for (int i = 0; i < a.length; i++) {
            StdOut.print(a[i] + " ");
        }
        StdOut.println();
    }

    /**
     * 测试数组是否已经有序
     * @param a     带测试数组
     * @return      测试结果: true-数组有序；false-数组无序
     */
    public static boolean isSorted(Comparable[] a) {
        // 测试数组是否已经有序
        for (int i = 1; i < a.length; i++) {
            if (less(a[i], a[i-1])) return false;
        }
        return  true;
    }

    public static void main(String[] args) {
        // 从标准输入读取字符串，将他们排序并输出
        String[] a = StdIn.readAllStrings();
        sort(a);
        assert isSorted(a);
        show(a);
    }
}
